package _interview100;

/**
 * 31. 下一个排列
 */
public class No31 {
    private int[] nums;

    public void nextPermutation(int[] nums) {
        this.nums = nums;
        int n = nums.length;
        for (int i = n - 2; i >= 0; i--) {
            if (nums[i] < nums[i + 1]) {
                for (int j = n - 1; j > i; j--) {
                    if (nums[j] > nums[i]) {
                        swap(i, j);
                        reverse(i + 1, n - 1);
                        return;
                    }
                }
            }
        }
        reverse(0, n - 1);
    }

    private void swap(int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    private void reverse(int l, int r) {
        while (l < r) swap(l++, r--);
    }
}
